import java.util.Arrays;

public class QuickSort {
    /*
    * 时间复杂度：O(N^2) 【数据有序或者逆序的情况】
    * 最好情况【每次可以均匀的分割待排序序列】：O(N * log2 N)
    * 空间复杂度：O(N)[单分支情况]
    * 最好：log2 N
    * 稳定性：不稳定
    * */
    public static void quickSort(int[] array){
        quick(array,0, array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        // 使用直接插入排序优化
        if(end -start+1 <=40){
            // 直接插入排序
            insertionSort(array,start,end);
            return;
        }

        // 在找基准之前，先确定 start 和 end 的 中间值。[三数取中法]
        int midValIndex = findMidValIndex(array,start,end);
        swap(array,start,midValIndex);
        int pivot = partiton(array,start,end);
        quick(array,start,pivot-1);// 递归左边
        quick(array,pivot+1,end);// 递归右边
    }
    // 直接插入排序
    public static void insertionSort(int[] array,int start,int end){
        for(int i = 1;i <= end;i++){
            int tmp = array[i];
            int j = i - 1;
            for( ; j >= start;j-- ){
                if(tmp < array[j]){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static int findMidValIndex(int[] array,int start,int end){
        // 确定 start 和 end 的中间下标
        int mid = start + ((end - start)>>>1);// == （start + end）/ 2
        // 确定 mid、start、end 三个下标，谁指向的元素是三个元素中的中间值
        if(array[end] > array[start]){
            if(array[start] > array[mid]){
                return start;
            }else if(array[mid] > array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            // array[start] >= array[end]
            if(array[end] > array[mid]){
                return end;
            }else if(array[mid] > array[start]){
                return start;
            }else {
                return mid;
            }
        }
    }
    private static void swap(int[] array,int x,int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    // 分割 - 找基准
    private static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            // 此时 end 下标 元素的值 是 小于 tmp的。
            array[start] = array[end];
            while(start<end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }
    // 有序
    public static void test1(int capacity){
        int[] array = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        quickSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    public static void main(String[] args) {
        test1(100_0000);
        int[] array = {6,1,2,7,9,3,4,5,10,6};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
